
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">















 
 
 
 
 
 
 
  
  


<html>
  <head>
    <script type="text/javascript" language="JavaScript">
    ORIGINAL_PAGE_PATH = "/appengine/articles/paging.html";
    </script>
    
    
<meta http-equiv="content-type" content="text/html; charset=utf-8"/>
<title>How-To Do Paging on App Engine - Google App Engine - Google Code</title>
<script type="text/javascript"><!--
(function(){function a(){this.t={};this.tick=function(c){this.t[c]=(new Date).getTime()};this.tick("start")}var b=new a;window.jstiming={Timer:a,load:b};if(window.external&&window.external.pageT)window.jstiming.pt=window.external.pageT;})();

var _tocPath_ = '/appengine/docs/_toc.ezt';
var codesite_token = null;
//--></script>
<link href="../../css/codesite.pack.04102009.css" type="text/css" rel="stylesheet"></link>
<script src="../../js/codesite_head.pack.04102009.js" type="text/javascript"></script>
<script type="text/javascript">CODESITE_CSITimer['load'].tick('bhs');</script>
<link rel="search" type="application/opensearchdescription+xml" title="Google Code" href="http://code.google.com/osd.xml" />

<!--[if IE]><link rel="stylesheet" type="text/css" href="../../css/iehacks.css" /><![endif]-->

    <link href="../../css/semantic_headers.css" rel="stylesheet" type="text/css" />
    <link href="../css/local_extensions.css" rel="stylesheet" type="text/css" />
  </head>

  <body class="gc-documentation">

    
    
    
</a>

<div id="gb">
 <span>
  
    <a id="lang-dropdown" class="dropdown" href="http://code.google.com" onclick="return false;"><img class="globeicon" src="../../images/globe2_small.png"/><span>English</span></a>
  
 </span>
</div>

<div class="gbh" style="left: 0pt;"></div>
<div class="gbh" style="right: 0pt;"></div>


<style type="text/css">
  #gc-topnav h1 {
    padding: 0 0 0 6px;
  }
</style>


<div id="gc-container">
<a name="top"></a>
<div id="skipto">
  <a href="#gc-pagecontent-anchor">Skip to page content</a>
  <a href="#gc-toc-anchor">Skip to main navigation</a>
</div>

<div id="gc-header">
  <div id="logo"><a href="http://code.google.com">
  
  
     <img src="../../images/cleardot.gif" height="1px" width="1px" alt="Google Code Home Page" id="gc-logo-img"/>
  
  
  </a></div>
  <div id="search">
    <div id="searchForm" class="searchForm">
      <form id="cse" action="http://www.google.com/cse" accept-charset="utf-8" class="gsc-search-box" onsubmit="executeGSearch(document.getElementById('gsearchInput').value); return false;">
      <noscript>
      <input type="hidden" name="cref" value="http://code.google.com/cse/googlecode-context.xml"/>
      </noscript>
        <table class="gsc-search-box" cellpadding="0" cellspacing="0">
          <tbody>
            <tr>
              <td class="gsc-input">
                <input id="gsearchInput" type="text" name="q" maxlength="2048" class="gsc-input" autocomplete="off" title="Google Code Search" style="width:345px"/>
              </td>
              <td class="gsc-search-button">
                <div id="cs-searchresults" onclick="event.cancelBubble = true;"></div>
                <input title="Search" id="gsearchButton" class="gsc-search-button" name="sa" value="Search" type="submit"/>
              </td>
            </tr>
            <tr>
              <td colspan="2" class="greytext">e.g. "templates" or "datastore"</td>
            </tr>
          </tbody>
        </table>
      </form>
    </div> <!-- end searchForm -->
  </div> <!-- end search -->
</div> <!-- end gc-header -->


<div id="codesiteContent">

<a name="gc-topnav-anchor"></a>
<div id="gc-topnav">
  <h1>Google App Engine</h1>
  <ul id="articles" class="gc-topnav-tabs">

    <li id="home_link">
      <a href="../index.html" title="Google App Engine home page">Home</a>
    </li>
  
    <li id="docs_link">
      <a href="../docs/index.html" title="Official Google App Engine documentation">Docs</a>
    </li>
  
    <li id="faq_link">
      <a href="../kb/index.html" title="Answers to frequently asked questions about Google App Engine">FAQ</a>
    </li>
  
    <li id="articles_link">
      <a href="index.html" class="selected" title="Focused articles and tutorials for Google App Engine developers">Articles</a>
    </li>
  
    <li>
      <a href="http://googleappengine.blogspot.com/" title="Official Google App Engine blog">Blog</a>
    </li>
  
    <li>
      <a href="../community.html" title="Community home for Google App Engine">Community</a>
    </li>
  
    <li>
      <a href="../terms.html" title="Google App Engine terms of service">Terms</a>
    </li>
  
    <li>
      <a href="../downloads.html" title="Download Google App Engine">Download</a>
    </li>
  

  </ul>
</div> <!-- end gc-topnav -->

    <div class="g-section g-tpl-170">

      <a name="gc-toc-anchor"></a>  
      <div class="g-unit g-first" id="gc-toc">
        <ul>
  <li><a href="../downloads.html">Downloads</a></li>
  <li><a href="http://code.google.com/status/appengine">System Status</a></li>
  <li><a href="http://code.google.com/p/googleappengine/issues/list">Issue Tracker</a></li>
</ul>
<div class="line"></div>
<ul>
  <li><h2>Getting Started</h2>
    <ul>
      <li><a href="../docs/whatisgoogleappengine.html">What Is Google App Engine?</a></li>
      <li><a href="../docs/java/gettingstarted/index.html">Java</a>
        <ul>
              <li><a href="../docs/java/gettingstarted/introduction.html">Introduction</a></li>
    <li><a href="../docs/java/gettingstarted/installing.html">Installing the Java SDK</a></li>
    <li><a href="../docs/java/gettingstarted/creating.html">Creating a Project</a></li>
    <li><a href="../docs/java/gettingstarted/usingusers.html">Using the Users Service</a></li>
    <li><a href="../docs/java/gettingstarted/usingjsps.html">Using JSPs</a></li>
    <li><a href="../docs/java/gettingstarted/usingdatastore.html">Using the Datastore with JDO</a></li>
    <li><a href="../docs/java/gettingstarted/staticfiles.html">Using Static Files</a></li>
    <li><a href="../docs/java/gettingstarted/uploading.html">Uploading Your Application</a></li>

        </ul>
      </li>
      <li><a href="../docs/python/gettingstarted/index.html">Python</a>
        <ul>
            <li><a href="../docs/python/gettingstarted/introduction.html">Introduction</a></li>
  <li><a href="../docs/python/gettingstarted/devenvironment.html">The Development Environment</a></li>
  <li><a href="../docs/python/gettingstarted/helloworld.html">Hello, World!</a></li>
  <li><a href="../docs/python/gettingstarted/usingwebapp.html">Using the webapp Framework</a></li>
  <li><a href="../docs/python/gettingstarted/usingusers.html">Using the Users Service</a></li>
  <li><a href="../docs/python/gettingstarted/handlingforms.html">Handling Forms With webapp</a></li>
  <li><a href="../docs/python/gettingstarted/usingdatastore.html">Using the Datastore</a></li>
  <li><a href="../docs/python/gettingstarted/templates.html">Using Templates</a></li>
  <li><a href="../docs/python/gettingstarted/staticfiles.html">Using Static Files</a></li>
  <li><a href="../docs/python/gettingstarted/uploading.html">Uploading Your Application</a></li>

        </ul>
      </li>
    </ul>
  </li>
</ul>
<div class="line"></div>
<ul>
  <li><h2>Java <sup class="new">Early Look</sup></h2>
    <ul>
          <li><a href="../docs/java/overview.html">Overview</a></li>
    <li><a href="../docs/java/runtime.html">Servlet Environment</a></li>
    <li><a href="../docs/java/datastore/index.html">Storing Data</a>
      <ul>
            <li><a href="../docs/java/datastore/overview.html">Overview</a></li>
    <li><a href="../docs/java/datastore/usingjdo.html">Using JDO</a></li>
    <li><a href="../docs/java/datastore/dataclasses.html">Defining Data Classes</a></li>
    <li><a href="../docs/java/datastore/creatinggettinganddeletingdata.html">Creating, Getting and Deleting Data</a></li>
    <li><a href="../docs/java/datastore/queriesandindexes.html">Queries and Indexes</a></li>
    <li><a href="../docs/java/datastore/transactions.html">Transactions</a></li>
    <li><a href="../docs/java/datastore/relationships.html">Relationships</a></li>
    <li><a href="../docs/java/datastore/usingjpa.html">Using JPA</a></li>
    <li><a href="../docs/java/javadoc/com/google/appengine/api/datastore/package-summary.html">Low-level API</a></li>

      </ul>
    </li>
    <li><a href="../docs/java/apis.html">Services</a>
      <ul>
        <li><a href="../docs/java/memcache/index.html">Memcache</a>
          <ul>
                <li><a href="../docs/java/memcache/overview.html">Overview</a></li>
    <li><a href="../docs/java/memcache/usingjcache.html">Using JCache</a></li>
    <li><a href="../docs/java/javadoc/com/google/appengine/api/memcache/package-summary.html">Low-level API</a></li>

          </ul>
        </li>
        <li><a href="../docs/java/urlfetch/index.html">URL Fetch</a>
          <ul>
                <li><a href="../docs/java/urlfetch/overview.html">Overview</a></li>
    <li><a href="../docs/java/urlfetch/usingjavanet.html">Using java.net</a></li>
    <li><a href="../docs/java/javadoc/com/google/appengine/api/urlfetch/package-summary.html">Low-level API</a></li>

          </ul>
        </li>
        <li><a href="../docs/java/mail/index.html">Mail</a>
          <ul>
                <li><a href="../docs/java/mail/overview.html">Overview</a></li>
    <li><a href="../docs/java/mail/usingjavamail.html">Using JavaMail</a></li>
    <li><a href="../docs/java/javadoc/com/google/appengine/api/mail/package-summary.html">Low-level API</a></li>

          </ul>
        </li>
        <li><a href="../docs/java/images/index.html">Images</a>
          <ul>
                <li><a href="../docs/java/images/overview.html">Overview</a></li>
    <li><a href="../docs/java/javadoc/com/google/appengine/api/images/package-summary.html">API Reference</a></li>

          </ul>
        </li>
        <li><a href="../docs/java/users/index.html">Google Accounts</a>
          <ul>
                <li><a href="../docs/java/users/overview.html">Overview</a></li>
    <li><a href="../docs/java/javadoc/com/google/appengine/api/users/package-summary.html">API Reference</a></li>

          </ul>
        </li>
      </ul>
    </li>
    <li><a href="../docs/java/javadoc/index.html">Javadoc Reference</a></li>
    <li><a href="../docs/java/jrewhitelist.html">JRE Class White List</a></li>
    <li><a href="../docs/java/config/index.html">Configuration</a>
      <ul>
            <li><a href="../docs/java/config/webxml.html">Deployment Descriptor</a></li>
    <li><a href="../docs/java/config/appconfig.html">App Config</a></li>
    <li><a href="../docs/java/config/indexconfig.html">Index Config</a></li>
    <li><a href="../docs/java/config/cron.html">Scheduled Tasks</a></li>

      </ul>
    </li>
    <li><a href="../docs/java/tools/index.html">Tools</a>
      <ul>
            <li><a href="../docs/java/tools/devserver.html">Development Server</a></li>
    <li><a href="../docs/java/tools/uploadinganapp.html">Uploading and Managing</a></li>
    <li><a href="../docs/java/tools/eclipse.html">Google Plugin for Eclipse</a></li>
    <li><a href="../docs/java/tools/ant.html">Using Apache Ant</a></li>

      </ul>
    </li>
    <li><a href="../docs/java/howto/index.html">How-To</a>
      <ul>
              <li><a href="../docs/java/howto/unittesting.html">Unit Testing</a></li>

      </ul>
    </li>

    </ul>
  </li>
</ul>
<div class="line"></div>
<ul>
  <li><h2>Python</h2>
    <ul>
          <li><a href="../docs/python/overview.html">Overview</a></li>
    <li><a href="../docs/python/runtime.html">CGI Environment</a></li>
    <li><a href="../docs/python/datastore/index.html">Storing Data</a>
      <ul>
             <li><a href="../docs/python/datastore/overview.html">Overview</a></li>
     <li><a href="../docs/python/datastore/entitiesandmodels.html">Entities and Models</a></li>
     <li><a href="../docs/python/datastore/creatinggettinganddeletingdata.html">Creating, Getting and Deleting Data</a></li>
     <li><a href="../docs/python/datastore/keysandentitygroups.html">Keys and Entity Groups</a></li>
     <li><a href="../docs/python/datastore/queriesandindexes.html">Queries and Indexes</a></li>
     <li><a href="../docs/python/datastore/transactions.html">Transactions</a></li>
     <li><a href="../docs/python/datastore/typesandpropertyclasses.html">Types and Property Classes</a></li>
     <li><a href="../docs/python/datastore/gqlreference.html">GQL Reference</a></li>

     <li><span class="tlw-title tlw-expanded">Reference</span>
       <ul>
         <li><a href="../docs/python/datastore/modelclass.html">Model</a></li>
         <li><a href="../docs/python/datastore/expandoclass.html">Expando</a></li>
         <li><a href="../docs/python/datastore/polymodelclass.html">PolyModel</a></li>
         <li><a href="../docs/python/datastore/propertyclass.html">Property</a></li>
         <li><a href="../docs/python/datastore/queryclass.html">Query</a></li>
         <li><a href="../docs/python/datastore/gqlqueryclass.html">GqlQuery</a></li>
         <li><a href="../docs/python/datastore/keyclass.html">Key</a></li>
         <li><a href="../docs/python/datastore/functions.html">Functions</a></li>
         <li><a href="../docs/python/datastore/exceptions.html">Exceptions</a></li>
       </ul>
     </li>

      </ul>
    </li>
    <li><a href="../docs/python/apis.html">Services</a>
      <ul>
        <li><a href="../docs/python/memcache/index.html">Memcache</a>
          <ul>
                 <li><a href="../docs/python/memcache/overview.html">Overview</a></li>
      <li><a href="../docs/python/memcache/usingmemcache.html">Using Memcache</a></li>
     <li><span class="tlw-title tlw-expanded">Reference</span>
       <ul>
         <li><a href="../docs/python/memcache/clientclass.html">Client</a></li>
         <li><a href="../docs/python/memcache/functions.html">Functions</a></li>
       </ul>
     </li>

          </ul>
        </li>
        <li><a href="../docs/python/urlfetch/index.html">URL Fetch</a>
          <ul>
                 <li><a href="../docs/python/urlfetch/overview.html">Overview</a></li>
     <li><span class="tlw-title tlw-expanded">Reference</span>
       <ul>
         <li><a href="../docs/python/urlfetch/fetchfunction.html">The fetch Function</a></li>
         <li><a href="../docs/python/urlfetch/responseobjects.html">Response Objects</a></li>
         <li><a href="../docs/python/urlfetch/exceptions.html">Exceptions</a></li>
       </ul>
     </li>

          </ul>
        </li>
        <li><a href="../docs/python/mail/index.html">Mail</a>
          <ul>
                 <li><a href="../docs/python/mail/overview.html">Overview</a></li>
     <li><a href="../docs/python/mail/sendingmail.html">Sending Mail</a></li>
     <li><a href="../docs/python/mail/attachments.html">Attachments</a></li>
     <li><span class="tlw-title tlw-expanded">Reference</span>
       <ul>
         <li><a href="../docs/python/mail/emailmessageclass.html">EmailMessage</a></li>
         <li><a href="../docs/python/mail/emailmessagefields.html">Message Fields</a></li>
         <li><a href="../docs/python/mail/functions.html">Functions</a></li>
         <li><a href="../docs/python/mail/exceptions.html">Exceptions</a></li>
       </ul>
     </li>

          </ul>
        </li>
        <li><a href="../docs/python/images/index.html">Images</a>
          <ul>
                 <li><a href="../docs/python/images/overview.html">Overview</a></li>
     <li><a href="../docs/python/images/installingPIL.html">Installing PIL</a></li>
     <li><a href="../docs/python/images/usingimages.html">Using the Images API</a></li>
     <li><span class="tlw-title tlw-expanded">Reference</span>
       <ul>
         <li><a href="../docs/python/images/imageclass.html">Image</a></li>
         <li><a href="../docs/python/images/functions.html">Functions</a></li>
         <li><a href="../docs/python/images/exceptions.html">Exceptions</a></li>
       </ul>
     </li>

          </ul>
        </li>
        <li><a href="../docs/python/users/index.html">Google Accounts</a>
          <ul>
                 <li><a href="../docs/python/users/overview.html">Overview</a></li>
     <li><a href="../docs/python/users/userobjects.html">User Objects</a></li>
     <li><a href="../docs/python/users/loginurls.html">Login URLs</a></li>
     <li><a href="../docs/python/users/adminusers.html">Admin Users</a></li>

     <li><span class="tlw-title tlw-expanded">Reference</span>
       <ul>
         <li><a href="../docs/python/users/userclass.html">User</a></li>
         <li><a href="../docs/python/users/functions.html">Functions</a></li>
         <li><a href="../docs/python/users/exceptions.html">Exceptions</a></li>
       </ul>
     </li>

          </ul>
        </li>
      </ul>
    </li>
    <li><a href="../docs/python/config/index.html">Configuration</a>
      <ul>
            <li><a href="../docs/python/config/appconfig.html">App Config</a></li>
    <li><a href="../docs/python/config/indexconfig.html">Index Config</a></li>
    <li><a href="../docs/python/config/cron.html">Scheduled Tasks</a></li>

      </ul>
    </li>
    <li><a href="../docs/python/tools/index.html">Tools</a>
      <ul>
            <li><a href="../docs/python/tools/devserver.html">Development Server</a></li>
    <li><a href="../docs/python/tools/uploadinganapp.html">Uploading and Managing</a></li>
    <li><a href="../docs/python/tools/uploadingdata.html">Uploading Data</a></li>
    <li><a href="../docs/python/tools/webapp/index.html">webapp Framework</a>
      <ul>
             <li><a href="../docs/python/tools/webapp/overview.html">Overview</a></li>
     <li><a href="../docs/python/tools/webapp/running.html">Running the Application</a></li>
     <li><a href="../docs/python/tools/webapp/requesthandlers.html">Request Handlers</a></li>
     <li><a href="../docs/python/tools/webapp/requestdata.html">Request Data</a></li>
     <li><a href="../docs/python/tools/webapp/buildingtheresponse.html">Building the Response</a></li>
     <li><a href="../docs/python/tools/webapp/redirects.html">Redirects, Headers and Status Codes</a></li>
     

     <li><span class="tlw-title tlw-expanded">Reference</span>
       <ul>
         <li><a href="../docs/python/tools/webapp/requestclass.html">Request</a></li>
         <li><a href="../docs/python/tools/webapp/responseclass.html">Response</a></li>
         <li><a href="../docs/python/tools/webapp/requesthandlerclass.html">RequestHandler</a></li>
         <li><a href="../docs/python/tools/webapp/wsgiapplicationclass.html">WSGIApplication</a></li>
         <li><a href="../docs/python/tools/webapp/utilmodule.html">Utility Functions</a></li>
         
       </ul>
     </li>

      </ul>
    </li>
    <li><a href="../docs/python/tools/libraries.html">Third-party Libraries</a></li>

      </ul>
    </li>
    <li><a href="../docs/python/howto/index.html">How-To</a>
      <ul>
              <li><a href="../docs/python/howto/usinggdataservices.html">Google Data Services</a></li>

      </ul>
    </li>

    </ul>
  </li>
</ul>
<div class="line"></div>
<ul>
  <li><h2>Managing Your App</h2>
    <ul>
      <li><a href="../docs/theadminconsole.html">The Admin Console</a></li>
      <li><a href="../docs/quotas.html">Quotas</a></li>
      <li><a href="../docs/billing.html">Billing</a></li>
    </ul>
  </li>
</ul>
<div class="line"></div>
<ul>
  <li><h2>Resources</h2>
    <ul>
      <li><a href="../kb/index.html">FAQ</a></li>
      <li><a href="index.html">Articles</a></li>
      <li><a href="http://appengine-cookbook.appspot.com/">Cookbook</a></li>
      <li><a href="http://appgallery.appspot.com/">App Gallery</a></li>
      <li><a href="http://code.google.com/p/googleappengine/">SDK Code</a></li>
      <li><a href="http://code.google.com/p/google-app-engine-samples/">Sample Apps Code</a></li>
      <li><a href="../community.html">Discussion Groups</a></li>
    </ul>
  </li>
</ul>
<div class="line"></div>
<ul>
  <li><a href="../docs/roadmap.html">Product Roadmap</a></li>
  <li><a href="http://code.google.com/p/googleappengine/wiki/SdkReleaseNotes">Release Notes</a></li>
  <li><a href="../docs/revision_history.html">Revision History</a></li>
</ul>

        <a class="hidden" href="#gc-topnav-anchor">More Google App Engine resource links</a>
      </div>
      
      <a name="gc-pagecontent-anchor"></a>   
      <div class="g-unit" id="gc-pagecontent">
        <script type="text/javascript">CODESITE_docEarlyProcessing();</script>
        <h1 class="page_title">How-To Do Paging on App Engine</h1>


<i>Joe Gregorio</i><br>
<i>December 18, 2008</i>

<div id="jd-content">
<div class="jd-descr">

<h2 id="intro">Introduction</h2>

<p>
One of the typical web functions you may need to do is pagination,
that is, displaying large datasets one page at a time.
If you have too many items to display on a single web page
you will display a subset of them, say 20, with a link to the next
page of 20 items. For example, the comments on a blog would be
paged if there are a lot of comments.
</p>

<h2 id="fetch">Fetch</h2>

<p>Now you may be tempted to use
<code>fetch(limit, offset=0)</code> to do your
paging, but this has limitations. From the documentation:
</p>

<blockquote><p><b>Note:</b> fetch() returns a maximum of 1000 results.
If more than 1000 entities match the query, and either no limit is
specified or a limit larger than 1000 is used, only the first 1000
results are returned by fetch().
</p></blockquote>

<p>
So you can use fetch() only if there are going to be less than 1000
entities. Even if you have less than 1000 entities you may still want to avoid it as the time
it takes grows as the value of offset increases. From the documentation:
</p>

<blockquote><p>The query has performance characteristics that correspond linearly with the offset amount plus the limit.</p></blockquote>

<h2 id="property">Paging on a property</h2>

<p>If your application needs more than that then you will need to do
something different. We will use a suggestion box as our working
example. We will start with a naive implementation and slowly
evolve it into a good working example of paging.
</p>
<pre class="prettyprint">PAGESIZE = 10

class Suggestion(db.Model):
  suggestion = db.StringProperty()
  when = db.DateTimeProperty(auto_now_add=True)
</pre>

<p>The first requirement for paging is having an indexed property that
you can run an inequality filter against. In this case let's
construct a way to page through the suggestions in reverse
chronological order. To get the first set of 10 suggestions:
</p>

<pre class="prettyprint">def get(self):
  suggestions = Suggestion.all().order("-when").fetch(PAGESIZE)

  # ..render template..
</pre>

<p>But we need to know if we should provide a "next" link to the
next page if there happens to be enough data for another page, so
let's request PAGESIZE+1 entities, and if we actually get back
PAGESIZE+1 entities then we know there are enough entities for
another page:</p>

<pre class="prettyprint">def get(self):
  <b>next = None</b>
  suggestions = Suggestion.all().order("-when").fetch(PAGESIZE + 1)
  <b>if len(suggestions) == PAGESIZE + 1:
    next = suggestions[-1].when
  suggestions = suggestions[:PAGESIZE]</b>

  # ..render template..
</pre>

<p>Now when we generate our HTML for the page of suggestions we can
use the value of <code>next</code> to determine whether or not to present a
<code>next</code> link. We also need a way to handle a request for the next
page, which we do by adding a query parameter <code>bookmark</code> that
contains the value of <code>when</code> that we should start the next page
at:</p>

<pre class="prettyprint">def get(self):
  next = None
  <b>bookmark = self.request.get("bookmark")
  if bookmark:
    suggestions = Suggestion.all().order("-when")
        .filter('when <=', bookmark).fetch(PAGESIZE+1)
  else:</b>
    suggestions = Suggestion.all().order("-when").fetch(PAGESIZE+1)
  if len(suggestions) == PAGESIZE+1:
    next = suggestions[-1].when
    suggestions = suggestions[:PAGESIZE]

  # ..render template..</pre>

<p>If you are paging and using a property that is unique across all
entities then you're done and the above code should work for
you. Unfortunately the code presented above has a problem for
this particular example because the value of the 'when' field isn't
guaranteed to be unique across all the entities, that is, it's
possible that more than one suggestion could come in at the exact
same time, as in this example:</p>

<table>
<tbody>
<tr>
<th>offset </th>
<th>suggestion</th>
<th>when</th>
</tr>
<tr>
<td>... </td>
<td>...</td>
<td>... </td>
</tr>
<tr>
<td>9 </td>
<td>Stock Jolt</td>
<td>2008-10-26 04:38:00</td>
</tr>
<tr>
<td style="background-color: rgb(252, 229, 205);"  >
10 </td>
<td style="background-color: rgb(252, 229, 205);"  >Allow
dogs in the office</td>
<td style="background-color: rgb(252, 229, 205);"  >
2008-10-26 03:35:58 </td>
</tr>
<tr>
<td style="background-color: rgb(252, 229, 205);"  >
11 </td>
<td style="background-color: rgb(252, 229, 205);"  >Allow
cats in the office</td>
<td style="background-color: rgb(252, 229, 205);"  >
2008-10-26 03:35:58 </td>
</tr>
<tr>
<td>12 </td>
<td>Buy some multicolored exercise balls</td>
<td>2008-10-26 01:10:03</td>
</tr>
<tr>
<td>13 </td>
<td>... </td>
<td>... </td>
</tr>
</tbody>
</table>

<p>If we present a page with the 10 most recent suggestions
you would end up with '2008-10-26 04:38:02' as the place to pick up the next 10 in the list.
Unfortunately #10 and #11 have the same value for 'when' and you would get overlap, 
the item at spot #10 appears as the last element on
the first page and also as the first element on the second page.
You can see how this problem would get worse the more duplicates
there were.</p>


<p>While we want to page in reverse chronological order, the 'when'
field may not be unique. What we need is a way to guarantee that it
is unique. One way to guarantee uniqueness is to have a single counter
that we increment each time we add a Suggestion entity to the
datastore. The value of the counter is appended to each 'when' value
and guarantees they are unique:</p>

<table>
<tbody>
<tr>
<th >offset</th>
<th >suggestion</th>
<th >when</th>
</tr>
<tr>
<td >...</td>
<td >...</td>
<td >...</td>
</tr>
<tr>
<td >9</td>
<td >Stock Jolt</td>
<td >2008-10-26 04:38:00|09</td>
</tr>
<tr>
<td style="background-color: rgb(252, 229, 205);" >
10<br /></td>
<td style="background-color: rgb(252, 229, 205);" >Allow
dogs in the office</td>
<td style="background-color: rgb(252, 229, 205);" >
2008-10-26 03:35:58|10<br /></td>
</tr>
<tr>
<td style="background-color: rgb(252, 229, 205);" >
11<br /></td>
<td style="background-color: rgb(252, 229, 205);" >Allow
cats in the office</td>
<td style="background-color: rgb(252, 229, 205);" >
2008-10-26 03:35:58|11</td>
</tr>
<tr>
<td >12</td>
<td >Buy some multicolored exercise balls</td>
<td >2008-10-26 01:10:03|12</td>
</tr>
<tr>
<td >13</td>
<td >...</td>
<td >...</td>
</tr>
</tbody>
</table>


<p>Let's update our model to reflect this change. We will have a
'created' property which is the date and time that the Suggestion
was created and change <code>when</code> to be a StringProperty since
it will now contain the date and time concatenated with another
string that makes it unique. The <code>when</code> property is the one we will
sort by when paginating.</p>

<pre class="prettyprint">class Suggestion(db.Model):
  suggestion = db.StringProperty()
  created = db.DateTimeProperty(auto_now_add=True)
  when = db.StringProperty()
</pre>



<p>If the rate at which you add suggestions is low then this is an
acceptable solution, but if they are coming in quickly then the
counter ends up becoming a bottleneck as it can only be updated so
quickly. We need a way to generate uniqueness but also allow quick
updates, and if you've read the article on counter sharding then this is a
familiar problem with a familiar solution. In this case we are
going to shard our counters over the users that are adding
suggestions and use the user id as part of the unique value we add
to each value of <code>when</code>.
</p>
<p>So we need a Contributor:
</p>

<pre class="prettyprint">class Contributor (db.Model):
   counter = db.IntegerProperty(default=0)

def unique_user(user):
  """
  Creates a unique string by using an increasing
  counter sharded per user.
  """
  email = user.email()

  def txn():
    contributor = Contributor.get_by_key_name(email)
    if contributor == None:
      contributor = Contributor(key_name=email)
    contributor.count += 1
    contributor.put()
    return contributor.count

  count = db.run_in_transaction(txn)

  return email + "|" + str(count)
</pre>


<p>Now this looks good:</p>


<table>
<tbody>
<tr>
<th>offset</th>
<th>suggestion</th>
<th>when</th>
</tr>
<tr>
<td>...</td>
<td>...</td>
<td>...</td>
</tr>
<tr>
<td>9</td>
<td>Stock Jolt</td>
<td>2008-10-26 04:38:00|joe@bitworking.org|1</td>
</tr>
<tr>
<td style="background-color: rgb(252, 229, 205);">10</td>
<td style="background-color: rgb(252, 229, 205);">Allow
dogs in the office</td>
<td style="background-color: rgb(252, 229, 205);">2008-10-26
03:35:58|fred@example.org|1</td>
</tr>
<tr>
<td style="background-color: rgb(252, 229, 205);">11</td>
<td style="background-color: rgb(252, 229, 205);">Allow
cats in the office</td>
<td style="background-color: rgb(252, 229, 205);">2008-10-26
03:35:58|joe@bitworking.org|2</td>
</tr>
<tr>
<td>12</td>
<td>Buy some multicolored exercise balls</td>
<td>2008-10-26 01:10:03|joe@bitworking.org|3</td>
</tr>
<tr>
<td>13</td>
<td>...</td>
<td>...</td>
</tr>
</tbody>
</table>

<p>But we do have one more problem, and that is that we now expose the
email address of the person making the suggestion in our <code>when</code>
value, which will get exposed in our 'next' link URI. To get around
that final problem we can obfuscate the data we append to each
<code>when</code> value by putting it through an MD5 hash:
</p>



<pre class="prettyprint">
def _unique_user(user):
  """
  Creates a unique string by using an increasing
  counter sharded per user. The resulting string
  is hashed to keep the users email address private.
  """
  email = user.email()

  def txn():
    contributor = Contributor.get_by_key_name(email)
    if contributor == None:
      contributor = Contributor(key_name=email)
    contributor.count += 1
    contributor.put()
    return contributor.count

  count = db.run_in_transaction(txn)

  return <b>hashlib.md5(</b> email + "|" + str(count)<b>).hexdigest()</b> </pre>


<table>
<tbody>
<tr>
<th>offset</th>
<th>suggestion</th>
<th>when</th>
</tr>
<tr>
<td>...</td>
<td >...</td>
<td>...</td>
</tr>
<tr>
<td>9</td>
<td >Stock Jolt</td>
<td>2008-10-26 04:38:00|aee15ab24b7b3718596e3acce04fba85</td>
</tr>
<tr>
<td style="background-color: rgb(252, 229, 205);">10</td>
<td style="background-color: rgb(252, 229, 205);" >Allow
dogs in the office</td>
<td style="background-color: rgb(252, 229, 205);">2008-10-26
03:35:58|404a3235076f6651914358680acf3cb5</td>
</tr>
<tr>
<td style="background-color: rgb(252, 229, 205);">11</td>
<td style="background-color: rgb(252, 229, 205);" >Allow
cats in the office</td>
<td style="background-color: rgb(252, 229, 205);">2008-10-26
03:35:58|7574b989df099d4e2b95619c9cf0c2a0</td>
</tr>
<tr>
<td>12</td>
<td >Buy some multicolored exercise balls</td>
<td>2008-10-26 01:10:03|c675e87cc990a718979afecc93a77bc1</td>
</tr>
<tr>
<td>13</td>
<td >...</td>
<td>...</td>
</tr>
</tbody>
</table>


<h2 id="no-property">Paging without a property</h2>

<p>All of the above is about paginating entities by a specific
property. If you just need to see all of the entities of a
particular kind and you either don't care about the order in which
they appear or the <code>__key__</code> order is sufficient, then you can do
your paging using the <code>__key__</code> property. The value of this property
is the entity key so you are guaranteed that it is unique, and you
don't need to use any of the techniques above to add 'uniqueness'
to it.</p>

<pre class="prettyprint">def get(self):
  next = None
  bookmark = self.request.get("__key__")
  if bookmark:
    suggestions = Suggestion.all().order("__key__").filter('__key__ >=', bookmark).fetch(PAGESIZE+1)
  else:
    suggestions = Suggestion.all().order("-when").fetch(PAGESIZE+1)
  if len(suggestions) == PAGESIZE+1:
    next = suggestions[-1].when
    suggestions = suggestions[:PAGESIZE]

  # ..render template..</pre>


<p>You can read more about the __key__ property and how to use
<a href="../docs/python/datastore/queriesandindexes.html#Queries_on_Keys">
in the App Engine documentation</a>.</p>

<h2 id="key-and-non-unique-property">Paging with <code>__key__</code> and a non-unique property</h2>

<p>The final example of paging is using the <code>__key__</code> property in
conjunction with a non-unique property. This technique is nice
because it doesn't require that addition of a new property to the
model, but it does require the addition of a new index, and it also
uses more queries so it is less efficient. If you would like to
read more about this technique Ryan Barrett posted
<a href="http://groups.google.com/group/google-appengine/browse_thread/thread/ee5afbde20e13cde">
a longer write-up to the Google App Engine discussion
group</a>.</p>

<h2 id="code">Code</h2>
<p>Code for this article can be found in the
<a href="http://code.google.com/p/google-app-engine-samples/source/browse/#svn/trunk/paging">
Google App Engine Samples project on code.google.com</a>
and it contains a full example of creating a unique index and also
a full example of paging with <code>__key__</code> and a non-unique
property.</p>

<h2 id="summary">Summary</h2>
<p>In summary, to do paging you need a property that has a unique
value for each entity and is indexed in the direction you want to
page. Always fetch N+1 entities to determine in you have enough
data for a 'next' page. And finally, if you don't have uniqueness
in the property then you can use a single counter, or counters
sharded over some attribute such as the user, to make that property
unique.
</p>
<h2 id="further-reading">Further Reading</h2>
<ul>
<li>Watch Brett Slatkin's presentation at Google I/O: <a href=
"http://sites.google.com/site/io/building-scalable-web-applications-with-google-app-engine">
Building Scalable Web Applications with Google App Engine</a></li>
<li><a href=
"../docs/python/datastore/queriesandindexes.html#Queries_on_Keys">
Read more about the __key__ property in the App Engine documentation</a>.</li>
</ul>

</div></div>
   
      </div><!-- end gc-pagecontent -->
   </div><!-- end gooey wrapper -->

    </div> <!-- end codesite content -->

<div id="gc-footer" dir="ltr">
  <div class="text">
    
      <div class="notice"><div id="notice" style="text-align: center; border: 1em 0em 1em 0em">
  Except as otherwise <a
  href="http://code.google.com/policies.html#restrictions">noted</a>,
  the content of this page is licensed under the <a rel="license"
  href="http://creativecommons.org/licenses/by/2.5/">Creative Commons
  Attribution 2.5 License</a>, and code samples are licensed under the
  <a rel="license" href="http://www.apache.org/licenses/LICENSE-2.0">Apache
  2.0 License</a>.
<!-- <rdf:RDF xmlns="http://web.resource.org/cc/" 
              xmlns:dc="http://purl.org/dc/elements/1.1/"
              xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#">
  <Work rdf:about="">
    <license rdf:resource="http://creativecommons.org/licenses/by/2.5/" />
  </Work>
  <License rdf:about="http://creativecommons.org/licenses/by/2.5/">
    <permits rdf:resource="http://web.resource.org/cc/Reproduction"/>
    <permits rdf:resource="http://web.resource.org/cc/Distribution"/>
    <requires rdf:resource="http://web.resource.org/cc/Notice"/>
    <requires rdf:resource="http://web.resource.org/cc/Attribution"/>
    <permits rdf:resource="http://web.resource.org/cc/DerivativeWorks"/>
  </License>
</rdf:RDF> -->
</div>
Java is a registered trademark of Sun Microsystems, Inc.</div>
    
    &copy;2009 Google -
    <a href="http://code.google.com">Code Home</a> -
    <a href="http://www.google.com/accounts/TOS">Terms of Service</a> -
    <a href="http://www.google.com/privacy.html">Privacy Policy</a> -
    <a href="http://code.google.com/more">Site Directory</a>
    <br /> <br />
    Google Code offered in:
    <a href="http://code.google.com/intl/en">English</a> -
    <a href="http://code.google.com/intl/es">Español</a> -
    <a href="http://code.google.com/intl/ja">日本語</a> -
    <a href="http://code.google.com/intl/ko">한국어</a> -
    <a href="http://code.google.com/intl/pt-BR">Português</a> -
    <a href="http://code.google.com/intl/ru">Pусский</a> -
    <a href="http://code.google.com/intl/zh-CN">中文(简体)</a> -
    <a href="http://code.google.com/intl/zh-TW">中文(繁體)</a>
  </div>
</div><!-- end gc-footer -->

</div><!-- end gc-containter -->

<script type="text/javascript">CODESITE_CSITimer['load'].tick('ats');</script>
<script src="../../js/codesite_tail.pack.04102009.js" type="text/javascript"></script>






  </body>
</html>


